1. Technical Field
The solution according to one or more embodiments of the present invention relates to the data-processing field. More specifically, this solution relates to computer graphics.
2. Description of Related Art
Computer graphics is a well-established technique for processing (e.g., designing, synthesizing, manipulating and rendering) visual content on computers. Computer graphics techniques are commonly used in a number of applications—such as Computer-Aided Design (CAD), Computer-Aided Manufacturing (CAM), Computer-Aided Engineering (CAE), medical imaging, video games, animation, and the like.
Generally, any image (consisting of an artifact mimicking a physical entity) is represented on a computer by a digital image, which may be either in a raster format (i.e., a matrix of pixels) or in a vector format (i.e., a set of basic graphic elements); the raster format provides greater realistic effects, whereas the vector format provides greater processing flexibility.
With reference in particular to computer graphics based on the vector format, the digital images are represented by models defining their graphic elements. For this purpose, free-form (or general) shapes (i.e., curves and/or surfaces) are commonly represented by models consisting of complex mathematical functions, such as B-splines or NURBSs (Non Uniform Rational Basis Splines), which provide high accuracy and sophistication for processing the corresponding free-form shapes.
However, in some applications it is desirable (or even necessary) to segment the free-form shapes into chains of circular elements approximating them. For example, in CAM applications, standard Computed Numerically Controlled (CNC) machines that are used to manufacture mechanical parts defined by the free-form shapes only recognize linear and circular motion commands; therefore, the free-form shapes have to be segmented into circular elements to machine the corresponding mechanical parts.
In any case, the mathematical functions of the above-mentioned models are quite complex; particularly, a generic spline is a piecewise polynomial function (i.e., it is defined by different polynomials depending on the value of its independent variables). Therefore, the models representing the free-form shapes involve a remarkable memory consumption for their storing (especially when they including a high number of splines); moreover, the evaluation of the mathematical functions of these models (for example, to render the corresponding free-form shapes or to control CNC machines) requires the application of numerical algorithms that are computationally complex and time-consuming.
Some techniques have been proposed in the art for segmenting two-dimensional (2D) free-form shapes—i.e., free-form curves—into chains of circular elements (including straight segments as degenerated circular arcs of infinite radius).
Particularly, U.S. Pat. No. 7,152,022 describes an algorithm to segment a complex curve representing a road into straight segments, circular arcs and clothoid arcs (i.e., portions of spiral curves whose curvature radius varies linearly along them). For this purpose, there is calculated a Ψ-s transform of the complex curve (plotting its tangent angles with respect to a fixed line along the complex curve). The Ψ-s transform is then fitted by straight segments and parabolic arcs. In this way, each horizontal straight segment, non-zero slope straight segment, and parabolic arc in the Ψ-s transform identifies a corresponding straight segment, circular arc and clothoid arc, respectively, in the complex curve. These portions of the complex curve are then used to calculate the curvature radius of each corresponding piece of the road.
“Approximation of Polygonal Curves with Min Number of Circular Arcs—Prototype Software”, Scot Drysdale et al., Algorithms for Complex Shapes with Certified Numerics and Topology, May 2005, Information Society Technologies instead discloses an algorithm for approximating an open polygonal curve (defined by a sequence of vertexes) with circular arcs, in order to describe the paths of cutting tools in CAM environments. For this purpose, there is defined a tolerance region (around the polygonal curve) that passes through a gate at each vertex (as defined by a segment centered around the vertex bisecting an angle formed with the adjacent vertices). All the valid circular arcs connecting two vertices (in the tolerance region) are then arranged in a direct graph. The shortest path in this graph from a first vertex to a last vertex determines the desired approximation of the polygonal curve.
Moreover, “Significant point detection and boundary representation with lines and circular arcs using a scanning box method”, Sung H. Yoon et al., IEEE Proceedings of South East con apos; 91 discloses an algorithm for representing a boundary curve by circular arcs, which algorithm is based on the detection of significant points of the boundary curve—defined as corner points and inflection points. Particularly, the corner points are detected (unlike other known approaches discussed in this document based on a k-curvature) by rotating the curve and using a scanning box to find its local extremes; the inflection points (wherein a convex arc joints a concave arc) are instead detected by curvature zero-crossing. Each segment between a pair of significant points is then represented with a circular arc by using a Least Mean Square (LMS) fitting method (with each segment providing an error larger than a threshold value that is split to define a new significant point). Similar neighboring circular arcs (in radius and center) are then merged when their difference is negligible. In this way, it is possible to maintain the location of dominant corner points and the length of circular arcs of the original curve.
However, the algorithms known in the art are not completely satisfactory. Indeed, the chain of circular arcs resulting from the segmentation of a generic free-form curve may include a very high number of small circular arcs. Therefore, the model representing the chain of circular arcs may be even more complex than the model representing the free-form curve.